package com.squirrel.michale;

import java.util.PriorityQueue;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/22 8:47 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode1642 {

    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int sum = 0;
        int heapSum = 0;
        for (int i = 1; i < heights.length; i++) {
            if (heights[i] > heights[i - 1]) {
                int delta = heights[i] - heights[i - 1];
                sum += delta;
                heap.offer(delta);
                heapSum += delta;
                if (heap.size() > ladders) {
                    heapSum -= heap.poll();
                }

                if (sum - heapSum > bricks) {
                    return i - 1;
                }
            }
        }
        return heights.length - 1;
    }

    public int furthestBuilding2(int[] heights, int bricks, int ladders) {

        int[] delta = new int[heights.length-1];

        int sum = 0;
        int index = 0;
        for (int i = 0; i < heights.length-1; i++) {
            delta[i] = heights[i + 1] - heights[i];
            if (delta[i] > 0) {
                sum += delta[i];
            }
            if (sum >= bricks && ladders > 0) {
                int max = 0;
                for (int j = 0; j <= i; j++) {
                    max = max > delta[j] ? max : delta[j];
                    delta[j] = 0;
                }
                sum -= max;
                ladders--;
            }
            if (sum > bricks) {
                index = i;
            }
        }
        return index;

    }

    public static void main(String[] args) {

        LeetCode1642 leetCode1642 = new LeetCode1642();

        int[] heights = new int[]{4,12,2,7,3,18,20,3,19};
        int bricks = 10, ladders = 2;


        System.out.println(leetCode1642.furthestBuilding(heights, bricks, ladders));


    }
}
